package org.example.algorithm.dp;

public class MaximalSquareSolution {

    public static void main(String[] args) {
        MaximalSquareSolution solution = new MaximalSquareSolution();
        char[][] matrix = {{'1'}};
        //char[][] matrix = {{'0','1'},{'1','0'}};
//        char[][] matrix = {
//                {'1', '0', '1', '0', '0'},
//                {'1', '0', '1', '1', '1'},
//                {'1', '1', '1', '1', '1'},
//                {'1', '0', '0', '1', '0'}
//        };
        int res = solution.maximalSquare3(matrix);
        System.out.println(res);
    }

    //暴力求解
    public int maximalSquare2(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int res = 0;
        for (int i=0;i<row;i++) {
            for (int j=0;j<col;j++) {
                if (matrix[i][j] == '1') {
                    res = Math.max(res, 1);
                    int maxSide = Math.min(row-i, col-j);
                    for (int k=1;k<maxSide;k++) {
                        boolean flag = true;
                        for (int m=0;m<=k;m++) {
                            if (matrix[i+k][j+m] == '0' || matrix[i+m][j+k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (!flag) {
                            break;
                        }
                        res = Math.max(res, (k+1)*(k+1));
                    }
                }
            }
        }
        return res;
    }

    //dp
    //dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        int maxSide = 0;
        for (int i=0;i<row;i++) {
            for (int j=0;j<col;j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    if (i==0 || j==0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                }
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
        return maxSide * maxSide;
    }

    //二维前缀和
    //参考：https://leetcode.cn/circle/discuss/UUuRex/
    //二维前缀和
    public int maximalSquare3(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] sum = new int[row+1][col+1];
        for (int i=0;i<row;i++) {
            for (int j=0;j<col;j++) {
                sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + matrix[i][j] - '0';
            }
        }
        int left = 0;
        int right = Math.min(row, col);
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if (checkSum(sum, row, col, mid)) {
                left = mid;
            } else {
                right = mid-1;
            }
        }
        return left*left;
    }

    private boolean checkSum(int[][] sum, int row, int col, int mid) {
        //mid代表边长
        //左上角(i,j)，右上角（i+mid-1,j+mid-1)
        int target = mid * mid;
        for (int i=0;i<=row-mid;i++) {
            for (int j=0;j<=col-mid;j++) {
                int product = sum[i+mid][j+mid] - sum[i+mid][j] - sum[i][j+mid] + sum[i][j];
                if (product == target) {
                    return true;
                }
            }
        }
        return false;
    }
}
